package org.mdrtwell.array;

/**
 * @author mdrtwell
 * 
 */
public class ArraySort {
	public static void main(String[] args) {
		ArraySort as = new ArraySort();
		as.maoPao(new int[] { 12, 5, 1, 6, 4, 9, 3, 23, 39, 403, 596, 87 });
		as.xunZe(new int[] { 12, 5, 1, 6, 4, 9, 3, 23, 39, 403, 596, 87 });
		as.chaRu(new int[] { 12, 5, 1, 6, 4, 9, 3, 23, 39, 403, 596, 87 });
		as.shell(new int[] { 12, 5, 1, 6, 4, 9, 3, 23, 39, 403, 596, 87 });
	}

	/**
	 * 冒泡法。 第一次确定索引0的元素，第二次确定索引1的元素...
	 * 
	 * @param source
	 */
	public void maoPao(int[] source) {
		for (int i = 0; i < source.length; i++) {
			for (int j = i + 1; j < source.length; j++) {
				// i 不变，j++，目的是要找到最小的放到第一位，然后是次小的放到第二位
				if (source[i] > source[j]) {
					int temp = source[i];
					source[i] = source[j];
					source[j] = temp;
				}
			}
			for (int k = 0; k < source.length; k++) {
				int temp = source[k];
				System.out.print(temp + " ");
			}
			System.out.println("\n");
		}
		System.out.println("Result:");
		for (int i : source) {
			System.out.print(i + " ");
		}
		System.out.println("");
	}

	/**
	 * j循环中不移动元素，只是记住索引就好了，最后找到最小的再置换
	 * 
	 * @param source
	 */
	public void xunZe(int[] source) {
		for (int i = 0; i < source.length; i++) {
			int lowerIndex = i;
			for (int j = i + 1; j < source.length; j++) {
				if (source[j] < source[lowerIndex]) {
					lowerIndex = j;
				}
			}
			int temp = source[i];
			source[i] = source[lowerIndex];
			source[lowerIndex] = temp;
		}
		for (int temp : source) {
			System.out.print(temp + " ");
		}
		System.out.println();
	}

	/**
	 * 插入法 第一轮i循环不能找到最小的。 找的是相对值。 小范围排序，扩大到大范围排序
	 * 
	 * @param source
	 */
	public void chaRu(int[] source) {
		for (int i = 1; i < source.length; i++) {
			for (int j = i; j > 0; j--) {
				if (source[j] < source[j - 1]) {
					int temp = source[j];
					source[j] = source[j - 1];
					source[j - 1] = temp;
				}
			}
		}
		for (int temp : source) {
			System.out.print(temp + " ");
		}
		System.out.println();
	}

	public static void shell(int[] source) {
		for (int increment = source.length / 2; increment > 0; increment /= 2) {
			for (int i = increment; i < source.length; i++) {
				int temp = source[i];
				int j = 0;
				for (j = i; j >= increment; j -= increment) {
					if (temp < source[j - increment]) {
						source[j] = source[j - increment];
					} else {
						break;
					}
				}
				source[j] = temp;
			}
		}
		for (int i : source) {
			System.out.print(i + " ");
		}
	}
}
